package com.dbh.alg.algorithm.hot100.普通数组;

/**
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 *
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,0]
 * 输出：3
 * 解释：范围 [1,2] 中的数字都在数组中。
 * 示例 2：
 *
 * 输入：nums = [3,4,-1,1]
 * 输出：2
 * 解释：1 在数组中，但 2 没有。
 * 示例 3：
 *
 * 输入：nums = [7,8,9,11,12]
 * 输出：1
 * 解释：最小的正数 1 没有出现。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * -231 <= nums[i] <= 231 - 1
 */
public class Leetcode41_缺失的第一个正数 {

    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 将数组中负数和大大于n的数置为n+1，因为这些数不影响最终结果
        // 如果数组中不存在负数或者大于n的数，那么最小数就是n+1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }

        // 利用数组中的索引进行标记,如果出现过的数组，将对应的索引位置数置为负数
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                if (nums[num - 1] > 0) {
                    nums[num - 1] = -nums[num -1];
                }
            }
        }

        // 第一个正数所在位置的索引+1就是缺失的数
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}
